Many computer vision problems involve assigning labels to image elements, such as pixels, texels, voxels, etc. In image restoration applications, labels associated with an image can be used to recover the original pixel intensities of the image. In this case, a label of a pixel within an image can indicate the intensity of the pixel. In stereo video applications, labels associated with a pair of stereo images can be used to reconstruct a three-dimensional image. In this case, labels can indicate depth information or disparity values. In image segmentation applications, labels associated with the pixels in an image can be used to indicate whether a pixel is part of the foreground or the background. Depending on the application, the label can be selected from two possible labels (a binary label situation) or from a larger number of labels (a multi-label situation). In some applications, the number of labels can be very large.
A number of energy minimization techniques have been developed for solving binary label and multi-label problems. For example, graph cut is one technique that can be used to optimize binary labels and can be extended to multi-label problems using an alpha expansion technique. However, alpha-expansion iteratively and exhaustively progresses through the number of labels and the number of pixels during, for example, image reconstruction. As the number of labels and the number of pixels increases, this results in slow reconstruction and computation times.